From Iteration to Recursion: Reframing the Mindset
Recursion is a methodology that fundamentally shifts how we approach problem-solving. When dealing with problems like summing lists,iteration(Code Listing 4-2) relies on an explicit accumulator theSum and loop state management; whereas recursion relies on a profound mathematical definition:
$$listsum(numList) = first(numList) + listsum(rest(numList))$$
Recursion is not merely a function calling itselfโit breaks down complex problems into smaller subproblems of the same structure, with its core lying in recognizing theself-similarity. Recursion execution consists of two symmetric phases:
- the "going down" phase: continuously slicing the list and pushing it onto the call stack until reaching a solvablebase case(Base Case).
- the "coming back" phase: starting from the simplest state, returning layer by layer and merging results upward.
Core Intuition
Iteration thinking is like 'grabbing a bucket and adding numbers one by one'; recursion thinking is 'if you can tell me the sum of the remaining numbers, I just need to add the first one.'